package com.example.demo.zaqizabatest.sortalgorithm;

/**
 *
 * 每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
 *
 * 对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，
 * 插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
 *
 * 插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。
 *
 * 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
 * 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
 * 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。
 *
 * @ClassName InsertionSort 插入排序
 * @Author lys4134
 * @Date 2021/12/29 09:48:31
 * @Description InsertionSort
 * @Version 1.0
 **/
public class InsertionBaseSort<T extends Comparable<T>> extends BaseSort<T> {

    @SuppressWarnings("AlibabaLowerCamelCaseVariableNaming")
    @Override
    public void sort(T[] nums) {
        final int N = nums.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                swap(nums, j, j - 1);
            }
        }
    }

    /**
     * 初始化数组{3, 5, 2, 4, 1}
     * 下面遍历
     * 1、{3, 5, 2, 4, 1}
     * 2、{3, 2, 5, 4, 1} -> {2, 3, 5, 4, 1}
     * 3、{2, 3, 4, 5, 1} -> {2, 3, 4, 5, 1} -> {2, 3, 4, 5, 1}
     * 4、{2, 3, 4, 1, 5} -> {2, 3, 1, 4, 5} -> {2, 1, 3, 4, 5} -> {1, 2, 3, 4, 5}
     *
     * @param nums
     */
    public void sort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j-1]) {
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        InsertionBaseSort<Integer> insertionSort = new InsertionBaseSort();
        int[] nums = new int[5];
        nums[0] = 3;nums[1] = 5;nums[2] = 2;nums[3] = 4;nums[4] = 1;
        insertionSort.sort(nums);
        insertionSort.print(nums);
    }
}